import java.util.*;

public class MyBinaryTree {
    static class TreeNode {
        public char val;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(char val) {
            this.val = val;
        }
    }

    public TreeNode createTree() {
        TreeNode A=new TreeNode('A');
        TreeNode B=new TreeNode('B');
        TreeNode C=new TreeNode('C');
        TreeNode D=new TreeNode('D');
        TreeNode E=new TreeNode('E');
        TreeNode F=new TreeNode('F');
        TreeNode G=new TreeNode('G');
        TreeNode H=new TreeNode('H');
        A.left=B;
        A.right=C;
        B.left=D;
        B.right=E;
        E.right=H;
        C.left=F;
        C.right=G;
        return A;
    }

    // 前序遍历
    void preOrder(TreeNode root) {
        if(root==null) return;
        System.out.print(root.val+" ");
        preOrder(root.left);
        preOrder(root.right);
    }
    // 中序遍历
    void inOrder(TreeNode root) {
        if(root==null) return;
        inOrder(root.left);
        System.out.print(root.val+" ");
        inOrder(root.right);
    }
    // 后序遍历
    void postOrder(TreeNode root) {
        if(root==null) return;
        postOrder(root.left);
        postOrder(root.right);
        System.out.print(root.val+" ");
    }

    //子问题思路求size(递归)
    public int size(TreeNode root) {
        if(root==null) return 0;
        return size(root.left) + size(root.right) + 1;
    }

    //遍历求size(也是递归)
    public static int nodeSize;
    public void size2(TreeNode root) {
        if(root==null) return;
        nodeSize++;
        size2(root.left);
        size2(root.right);
    }

    //子问题思路(整棵树的叶子结点个数=左子树的叶子结点个数+右子树的叶子结点个数)
    public int leafNodeSize(TreeNode root) {
        if(root==null) return 0;
        if(root.left==null && root.right==null) return 1;
        return leafNodeSize(root.left)+leafNodeSize(root.right);
    }

    //遍历思路(以某种方式遍历,只要找到一个就++)
    public static int leafNodeCount;
    public void leafNodeSize2(TreeNode root) {
        if(root==null) return;
        if(root.left==null && root.right==null) leafNodeCount++;
        leafNodeSize2(root.left);
        leafNodeSize2(root.right);
    }

    //计算第k层有多少个节点
    public int getKLevelNodeSize(TreeNode root,int k) {
        if(root==null) return 0;
        if(k==1) return 1;
        return getKLevelNodeSize(root.left,k-1)+getKLevelNodeSize(root.right,k-1);
    }

    //求树的高度
    public int getHeight(TreeNode root) {
        //就等于左子树右子树的最大高度+1
        if(root==null) return 0;
        int leftHeight=getHeight(root.left);
        int rightHeight=getHeight(root.right);
        return Math.max(leftHeight,rightHeight)+1;
    }

    //遍历二叉树,找到val所在节点
    public TreeNode find(TreeNode root,char val) {
        if(root==null) return null;
        if(root.val==val)  {
            return root;
        }
        TreeNode leftNode=find(root.left,val);
        if(leftNode!=null) return leftNode;
        TreeNode rightNode=find(root.right,val);
        if(rightNode!=null) return rightNode;
        return null;//前两个if语句都没有进去,最后return null
    }


    /**
     * 104. 二叉树的最大深度
     * @param root
     * @return
     */
    public int maxDepth(TreeNode root) {
        //就等于左子树右子树的最大高度+1
        if(root==null) return 0;
        int leftHeight=maxDepth(root.left);
        int rightHeight=maxDepth(root.right);
        return leftHeight>rightHeight?leftHeight+1:rightHeight+1;
    }

    /**
     * 100. 相同的树
     * @param p
     * @param q
     * @return
     */
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if(p==null && q!=null || p!=null && q==null) {
            return false;
        }
        //经过上面的if后,两棵树要么都为空,要么都不为空
        if(p==null && q==null) return true;

        if(p.val!=q.val) return false;//两者都不为空时判断值是否相等
        return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);
    }

    /**
     * 572. 另一棵树的子树
     * 时间复杂度为m*n,因为对于p的每一个节点,都要与q进行n次比较
     * @param root
     * @param subRoot
     * @return
     */
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        //虽然题目给定的root的范围大于1,但是递归过程中root仍可能遍历到null,若此时还没有检测搭配与subRoot相同的部分,则说明root根本就不包含subRoot,所以返回false
        if(root==null) return false;
        if(isSameTree(root,subRoot))return true;//这个就是递归的终止条件
        if(isSubtree(root.left,subRoot))return true;
        if(isSubtree(root.right,subRoot))return true;
        return false;
    }

    /**
     * 226. 翻转二叉树
     * @param root
     * @return
     */
    public TreeNode invertTree(TreeNode root) {
        //还是用递归思想,遍历每一个节点,交换其子树的位置,直到遍历到null
        if(root==null) return null;
        TreeNode ret=root.left;
        root.left=root.right;
        root.right=ret;

        //开始递归
        invertTree(root.left);
        invertTree(root.right);
        return root;
    }

    /**
     * 110. 平衡二叉树
     * @param root
     * @return
     */
    public boolean isBalanced(TreeNode root) {
        if(root==null)return true;
        int leftHeight=maxDepth2(root.left);
        int rightHeight=maxDepth2(root.right);
        return Math.abs(leftHeight-rightHeight)<=1 && isBalanced(root.left)&& isBalanced(root.right);
    }
    public int maxDepth2(TreeNode root) {
        if(root==null)return 0;
        int leftTree=maxDepth(root.left);
        int rightTree=maxDepth(root.right);
        return leftTree>rightTree?leftTree+1:rightTree+1;
    }

    /**
     * 101. 对称二叉树
     * @param root
     * @return
     */
    public boolean isSymmetric(TreeNode root) {
        return isSymmetricChild(root.left,root.right);
    }

    public boolean isSymmetricChild(TreeNode leftTree,TreeNode rightTree) {
        //检查结构是否对称
        if(leftTree!=null && rightTree==null || rightTree!=null && leftTree==null ) {
            return false;
        }
        //结构相同之两个都为空
        if(leftTree==null && rightTree==null)return true;
        //结构相同之两个都不为空,接着判断值是否相等
        if(leftTree.val!=rightTree.val)return false;
        //继续判断子节点的对称情况
        return isSymmetricChild(leftTree.left,rightTree.right) &&
                isSymmetricChild(leftTree.right,rightTree.left);
    }

    public void levelOrder(TreeNode root) {
        Queue<TreeNode> queue=new LinkedList<>();
        if(root==null)return;
        queue.offer(root);//将根节点压入队列
        while(!queue.isEmpty()) {
            TreeNode cur=queue.poll();
            System.out.print(cur.val+" ");
            if(cur.left!=null) {
                queue.offer(cur.left);
            }
            if(cur.right!=null) {
                queue.offer(cur.right);
            }
        }
        System.out.println();
    }


    /*
    public List<List<Integer>> levelOrder2(TreeNode root) {
        List<List<Integer>> ret=new ArrayList<>();
        if(root==null)return ret;
        Queue<TreeNode> queue=new LinkedList<>();
        queue.offer(root);//将根节点压入队列
        while(!queue.isEmpty()) {
            int size=queue.size();
            List<Integer> list=new ArrayList<>();
            while(size>0) {
                TreeNode cur=queue.poll();
                list.add(cur.val);//因为在一开始定义的cTreeNode是char类型的,所以这里会报错
                if(cur.left!=null) {
                    queue.offer(cur.left);
                }
                if(cur.right!=null) {
                    queue.offer(cur.right);
                }
                size--;
            }
            ret.add(list);
        }
        return ret;
    }

     */


    //判断一棵树是否是完全二叉树
    boolean isCompleteTree(TreeNode root) {
        Queue<TreeNode> queue=new LinkedList<>();
        if(root==null) return true;//空时认为是完全二叉树
        queue.offer(root);
        while(!queue.isEmpty()) {
            TreeNode cur=queue.poll();
            if(cur==null) { //当cur为空时,跳出循环
                break;
            }
            queue.offer(cur.left);//cur不为空时,把左右节点压入队列中,不用判断是否为空,因为null也要压入队列
            queue.offer(cur.right);
        }
        //break出来
        while(!queue.isEmpty()) {
            TreeNode tmp=queue.peek();
            if(tmp!=null) {
                return false;
            }
            else {
                queue.poll();
            }
        }
        return true;
    }

    /**
     * 236 二叉树的最近公共祖先
     * @param root
     * @param p
     * @param q
     * @return
     */
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root==null)return null;
        if(root==p || root==q)return root;//这是递归终止条件,找到了p或q中的一个,然后停止递归
        TreeNode leftTree=lowestCommonAncestor(root.left,p,q);//去左子树找p,q
        TreeNode rightTree=lowestCommonAncestor(root.right,p,q);//去右边找p,q

        if(leftTree!=null && rightTree!=null) {
            return root;
        }
        else if(leftTree!=null){
            return leftTree;//在左子树都找到了
        }
        else {
            return rightTree;//都在右子树
        }
    }

    public TreeNode lowestCommonAncestor2(TreeNode root, TreeNode p, TreeNode q) {
        if(root==null) return null;
        Stack<TreeNode> stackP=new Stack<>();
        getPath(root,p,stackP);
        Stack<TreeNode> stackQ=new Stack<>();
        getPath(root,q,stackQ);
        //上述代码执行完成,栈中已经存放了路径上的所有节点
        int sizeP= stackP.size();
        int sizeQ= stackQ.size();
        if(sizeP>sizeQ) {
            int size=sizeP-sizeQ;
            while(size!=0) {
                stackP.pop();
                size--;
            }
        }else {
            int size=sizeQ-sizeP;
            while(size!=0) {
                stackQ.pop();
                size--;
            }
        }
        //if-else执行完成后,两栈的节点个数相等了
        while(!stackP.isEmpty() && !stackQ.isEmpty()) {
            if(stackP.peek()==stackQ.peek()) {
                return stackP.peek();//peek一下,一样的话就返回
            }else { //不一样的话继续出
                stackP.pop();
                stackQ.pop();
            }
        }
        return null;
    }
    //将root到指定节点的路径存放到栈中
    public boolean getPath(TreeNode root, TreeNode node, Stack<TreeNode> stack) {
        /*
        如何知道路径是正确的?也就是说如何确定路径上的节点?
        当现在这个节点不是,这个节点左树没有指定节点,右树也没有时就可以确定这个节点不在路径上,要弹出
         */
        if(root==null)return false;//空树
        stack.push(root);
        if(root==node) return true;
        boolean flg=getPath(root.left,node,stack);
        if(flg) return true;

        boolean flg2=getPath(root.right,node,stack);
        if(flg2) return true;

        stack.pop();//该节点的左右都走了一遍,都没有,那么弹出该节点
        return false;
    }

    //前序遍历的非递归实现
    public void preOrderNot(TreeNode root) {
        Stack<TreeNode> stack=new Stack<>();
        TreeNode cur=root;
        while(cur!=null || !stack.isEmpty()) {
            while(cur!=null) {
                stack.push(cur);
                System.out.print(cur.val+" ");
                cur=cur.left;
            }
            TreeNode top=stack.pop();
            cur=top.right;
        }
    }

    //中序遍历的非递归实现
    public void inOrderNot(TreeNode root) {
        Stack<TreeNode> stack=new Stack<>();
        TreeNode cur=root;
        while(cur!=null || !stack.isEmpty()) {
            while(cur!=null) {
                stack.push(cur);
                cur=cur.left;
            }
            TreeNode top=stack.pop();
            System.out.print(top.val+" ");
            cur=top.right;
        }
    }

    //后序遍历的非递归实现
    public void postOrderNot(TreeNode root) {
        Stack<TreeNode> stack=new Stack<>();
        TreeNode cur=root;
        TreeNode prev=null;
        while(cur!=null || !stack.isEmpty()) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            TreeNode top = stack.peek();
            if (top.right == null || prev==top.right) {
                //当top没有右节点时才能打印当前top
                stack.pop();
                System.out.print(top.val + " ");
                prev=top;
            } else {
                //当top右边不为空时不能弹出
                cur = top.right;
            }
        }
    }


    /*

    //105.从前序与中序遍历序列构造二叉树
    public int preIndex;
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return buildTreeChild(preorder,inorder,0,inorder.length-1);
    }

    private TreeNode buildTreeChild(int[] preorder,int[] inorder,int inBegin,int inEnd) {
        if(inBegin>inEnd)return null;//当inEnd走到inBegin的左边时,说明该节点无子树,直接返回null
        TreeNode root=new TreeNode(preorder[preIndex]);//将前序遍历的第一个节点作为根节点
        //在inorder数组中的(inBegin,inEnd)之间寻找值为preorder[preIndex]的节点
        int rootIndex=findRootIndex(inorder,inBegin,inEnd,preorder[preIndex]);
        preIndex++;//找到一个root之后,前序数组遍历到下一个节点
        root.left=buildTreeChild(preorder,inorder,inBegin,rootIndex-1);//inBegin没变,inEnd变为root的左节点
        root.right=buildTreeChild(preorder,inorder,rootIndex+1,inEnd);//inEnd没变,inBegin变为root的右节点

        return root;
    }

    private int findRootIndex(int[] inorder,int inBegin,int inEnd,int key) {
        for(int i=inBegin;i<=inEnd;i++) {
            if(inorder[i]==key) {
                return i;
            }
        }
        return -1;
    }

     */


    /*
    106.从中序与后序遍历构造二茶壶
    public int postIndex=0;
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        postIndex=postorder.length-1;//postIndex应从postorder数组最左边开始
        return buildTreeChild(inorder,postorder,0,postorder.length-1);
    }
    private TreeNode buildTreeChild(int[] inorder,int[] postorder,int inBegin,int inEnd) {
        if(inBegin>inEnd)return null;
        TreeNode root=new TreeNode(postorder[postIndex]);
        int rootIndex=findRootIndex(inorder,inBegin,inEnd,postorder[postIndex]);
        postIndex--;
        root.right=buildTreeChild(inorder,postorder,rootIndex+1,inEnd);//这次要先创建右树,再创建左树
        root.left=buildTreeChild(inorder,postorder,inBegin,rootIndex-1);
        return root;
    }

    private int findRootIndex(int[] inorder,int inBegin,int inEnd,int key) {
        for(int i=inBegin;i<=inEnd;i++) {
            if(inorder[i]==key) {
                return i;
            }
        }
        return -1;
    }

     */


    /**
     * 606.根据二叉树创建字符串
     * @param root
     * @return
     */
    public String tree2str(TreeNode root) {
        StringBuilder stringBuilder=new StringBuilder();
        tree2strChild(root,stringBuilder);
        return stringBuilder.toString();
    }
    private void tree2strChild(TreeNode root,StringBuilder stringBuilder) {
        if(root==null)return;
        stringBuilder.append(root.val);
        //处理左树
        if(root.left!=null) {   //左子树不为空
            stringBuilder.append("(");//左树不为空,先加左括号
            tree2strChild(root.left,stringBuilder);//递归左子树
            stringBuilder.append(")");//递归完后加右括号
        }else {
            if(root.right==null) {  //左右子树都为空
                return;
            }else {     //左子树为空,右子树不为空时,要加一个()为左子树占位
                stringBuilder.append("()");
            }
        }
        //处理右树
        if(root.right==null) {
            return;//右树位空时不用加()占位
        }else {
            stringBuilder.append("(");//右树不为空,先加左括号
            tree2strChild(root.right,stringBuilder);//递归右子树
            stringBuilder.append(")");//递归完后加右括号
        }
    }


}
